package _03_图;

import java.util.*;

/*
    邻接表实现的图
 */
public class ListGraph<V,E> implements Graph<V,E>{
    //存放顶点的数量
    private Map<V,Vertex<V,E>> vertices = new HashMap<>();
    //存放边的数量
    private Set<Edge<V,E>> edges = new HashSet<>();

    //顶点的内部类
    private static class Vertex<V,E>{
        V value; //顶点上存储的数据
        Set<Edge<V,E>> inEdges = new HashSet<>(); //从该顶点进入的边
        Set<Edge<V,E>> outEdges = new HashSet<>(); //从该顶点出的边
        Vertex(V value){
            this.value = value;
        }

        @Override
        public boolean equals(Object obj) {
            //比较两个顶点的值是否相等
            return Objects.equals(value,((Vertex<V,E>)obj).value);
        }

        @Override
        public int hashCode() {
            return value == null ? 0 : value.hashCode();
        }

        @Override
        public String toString() {
            return value == null ? "null" : value.toString();
        }
    }

    //边的内部类
    private static class Edge<V,E>{
        Vertex<V,E> from;
        Vertex<V,E> to;
        E weight; //权值

        public Edge(Vertex<V,E> from, Vertex<V,E> to){
            this.from = from;
            this.to = to;
        }

        @Override
        public boolean equals(Object obj) {
            //判断两个边的起点和终点是否一样
            Edge<V,E> edge = (Edge<V,E>) obj;
            return from.equals(edge.from) && to.equals(edge.to);
        }

        @Override
        public int hashCode() {
            return from.hashCode() * 31 + to.hashCode();
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }

    //顶点的数量
    @Override
    public int verticesSize() {
        return vertices.size();
    }
    //边的数量
    @Override
    public int edgesSize() {
        return edges.size();
    }

    //增加一个顶点
    @Override
    public void addVertex(V v) {
        if(vertices.containsKey(v)) return;
        vertices.put(v,new Vertex<>(v));
    }

    //删除一个顶点
    @Override
    public void removeVertex(V v) {
        //删除顶点所在的边
        Vertex<V,E> vertex = vertices.remove(v);
        if(vertex == null) return; //顶点不存在，就返回

        //删除顶点所在的边,使用迭代器
        //先删除出去的边
        //拿到每一个边的对象
        Iterator<Edge<V, E>> iterator1 = vertex.outEdges.iterator();
        while(iterator1.hasNext()){
             Edge<V,E> edge = iterator1.next();
             edge.to.inEdges.remove(edge); //将这条边出去到达的顶点的边的集合，在它的集合将这条边删除
             iterator1.remove(); //将当前边删除
            edges.remove(edge); //从大集合删除
        }

        //在删除出去的边
        Iterator<Edge<V, E>> iterator2 = vertex.inEdges.iterator();
        while(iterator2.hasNext()){
            Edge<V,E> edge = iterator2.next();
            edge.from.outEdges.remove(edge); //将这条边出去到达的顶点的边的集合，在它的集合将这条边删除
            iterator2.remove(); //将当前边删除
            edges.remove(edge); //从大集合删除
        }
    }

    //增加一条边，起点 和 终点
    @Override
    public void addEdge(V fromVm, V toV) {
        addEdge(fromVm, toV,null);
    }

    //增加一条边 起点 和 终点  包括权值
    @Override
    public void addEdge(V fromV, V toV, E weight) {
        //判断from,to顶点是否存在
        Vertex<V,E> fromVertex = vertices.get(fromV);
        if(fromVertex == null){
            //不存在就创建添加
            fromVertex = new Vertex<>(fromV);
            vertices.put(fromV,fromVertex);
        }
        Vertex<V,E> toVertex = vertices.get(toV);
        if(toVertex == null){
            //不存在就创建添加
            toVertex = new Vertex<>(toV);
            vertices.put(toV,toVertex);
        }
        //新创建一条边对象
        Edge<V,E> edge = new Edge<>(fromVertex,toVertex);
        edge.weight = weight; //增加权值
        //因为哈希Set不好取出对应的元素，只能遍历取，效率低下
        //所以，我们的做法是:不管以前是否有这条边，我们都将其删掉，然后重新创建
        //哈希Set删除逻辑就是比较两个顶点
        //两个方向都要删除,逻辑删除，返回真，两个才会真删除,否则代表没有。不用删除，节省性能
        if(fromVertex.outEdges.remove(edge)){
            toVertex.inEdges.remove(edge);
            edges.remove(edge);
        }
        //两个方向都要新增
        fromVertex.outEdges.add(edge);
        toVertex.inEdges.add(edge);
        edges.add(edge);
    }

    //删除一条边
    @Override
    public void removeEdge(V fromV, V toV) {
        //先判断两个顶点是否存在
        Vertex<V,E> fromVertex = vertices.get(fromV);
        if(fromVertex == null) return;

        Vertex<V,E> toVertex = vertices.get(toV);
        if(toVertex == null) return;

        //在看这两个顶点是否有边存在
        Edge<V,E> edge = new Edge<>(fromVertex,toVertex);
        //先判断是否有起点这点边
        if(fromVertex.outEdges.remove(edge)){
            toVertex.inEdges.remove(edge);
            edges.remove(edge);
        }
    }

    public void print() {
        System.out.println("[顶点]-------------------");
        vertices.forEach((V v, Vertex<V, E> vertex) -> {
            System.out.println(v);
            System.out.println("out-----------");
            System.out.println(vertex.outEdges);
            System.out.println("in-----------");
            System.out.println(vertex.inEdges);
        });

        System.out.println("[边]-------------------");
        edges.forEach((Edge<V, E> edge) -> {
            System.out.println(edge);
        });
    }
}
